package com.lw.leetcode.arr.b;

import java.util.ArrayList;
import java.util.List;

/**
 * arr
 * 417. 太平洋大西洋水流问题
 *
 * @Author liw
 * @Date 2021/6/12 21:29
 * @Version 1.0
 */
public class PacificAtlantic {

    public static void main(String[] args) {
        PacificAtlantic test = new PacificAtlantic();
//        int[][] arr = {{1,1},{1,1},{1,1}};

        // [[0,4],[0,5],[1,4],[1,5],[2,5],[4,4],[9,2],[19,4],[19,5],[20,2],[20,3],[20,4],[21,4],[22,4],[23,5],[24,5],[25,4],[25,5],[26,0],[26,1],[28,0]]
        int[][] arr = {
                {16, 19, 15, 2, 17, 7},
                {13, 5, 14, 4, 8, 7},
                {2, 11, 18, 13, 1, 16},
                {18, 15, 12, 15, 4, 11},
                {19, 14, 11, 17, 18, 13},
                {17, 16, 11, 10, 15, 14},
                {18, 17, 7, 8, 9, 11},
                {2, 9, 19, 0, 14, 12},
                {5, 18, 5, 11, 5, 1},
                {5, 7, 15, 13, 0, 15},
                {1, 14, 4, 16, 1, 9},
                {19, 17, 3, 19, 16, 10},
                {6, 3, 15, 11, 9, 5},
                {3, 4, 3, 10, 4, 7},
                {14, 16, 3, 8, 2, 10},
                {18, 5, 2, 9, 0, 7},
                {13, 7, 9, 7, 18, 13},
                {0, 15, 13, 15, 10, 16},
                {2, 12, 5, 11, 13, 15},
                {17, 16, 13, 13, 14, 19},
                {17, 14, 15, 14, 13, 0},
                {11, 12, 13, 0, 11, 0},
                {1, 3, 4, 7, 9, 8},
                {3, 5, 12, 7, 7, 15},
                {0, 14, 1, 5, 9, 13},
                {12, 14, 4, 13, 16, 13},
                {18, 18, 13, 4, 6, 9},
                {2, 0, 7, 13, 11, 7},
                {19, 18, 1, 6, 18, 0}};

        // [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
        // [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
//        int[][] arr = {
//                {1,2,2,3,5},
//                {3,2,3,4,4},
//                {2,4,5,3,1},
//                {6,7,1,4,5},
//                {5,1,1,2,4}};

        List<List<Integer>> lists = test.pacificAtlantic(arr);
        System.out.println(lists);
    }


    private int aa;
    private int bb;
    private int[][] heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> list = new ArrayList<>();
        int a = heights.length;
        if (a == 0) {
            return list;
        }
        int b = heights[0].length;
        if (b == 0) {
            return list;
        }
        aa = a - 1;
        bb = b - 1;
        this.heights = heights;
        boolean[][] b1 = new boolean[a][b];
        boolean[][] b2 = new boolean[a][b];
        for (int i = 0; i < a; i++) {
            b1[i][0] = true;
            b2[i][bb] = true;
        }
        for (int i = 0; i < b; i++) {
            b1[0][i] = true;
            b2[aa][i] = true;
        }
        for (int i = 0; i < a; i++) {
            find(b1, i, 1, heights[i][0]);
            find(b2, i, b - 2, heights[i][bb]);
        }
        for (int i = 0; i < b; i++) {
            find(b1, 1, i, heights[0][i]);
            find(b2, a - 2, i, heights[aa][i]);
        }

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                if (b1[i][j] && b2[i][j]) {
                    List<Integer> item = new ArrayList<>(2);
                    item.add(i);
                    item.add(j);
                    list.add(item);
                }
            }
        }
        return list;
    }


    private void find(boolean[][] arr, int x, int y, int value) {
        if (x < 0 || x > aa || y < 0 || y > bb) {
            return;
        }
        if (arr[x][y]) {
            return;
        }
        int v = heights[x][y];
        if (v < value) {
            return;
        }
        arr[x][y] = true;
        find(arr, x - 1, y, v);
        find(arr, x + 1, y, v);
        find(arr, x, y - 1, v);
        find(arr, x, y + 1, v);
    }


}
